// 1.dp判断是否回文串
class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        vector<vector<int>> dp(n, vector<int>(n, 1));
        /*
        真正有意义的只有上三角（含对角线）。
        下三角是不是 1 不重要，通常不会被访问。
        */
        int max_size = 0;
        pair<int, int> temp={0,0};
        for(int i = n-2; i >= 0; --i) {
            for(int j = i+1; j < n; ++j) {
                dp[i][j] = (s[i] == s[j]) && dp[i+1][j-1]; 
                //因为 dp[i][j] 依赖 dp[i+1][j-1]，所以必须 i 从后往前，j 从前往后。
                if(dp[i][j] == 1 && j-i > max_size) {
                    temp.first = i;
                    temp.second = j;
                    max_size = j-i;
                }

            }
        }
        string result = s.substr(temp.first, temp.second-temp.first+1);
        
        return result;
    }
};

// 2.中心扩展法
class Solution {
public:
    int max_size = 0;
    pair<int, int> temp{0,0};

    void act(string& s, int left, int right) {
        while (left >= 0 && right < s.size() && s[left] == s[right]) {
            if (right - left + 1 > max_size) {
                max_size = right - left + 1;
                temp.first = left;
                temp.second = right;
            }
            left--;
            right++;
        }
    }

    string longestPalindrome(string s) {
        int n = s.size();
        for (int i = 0; i < n; ++i) {
            act(s, i, i);     // 奇数长度中心
            act(s, i, i+1);   // 偶数长度中心
        }
        return s.substr(temp.first, temp.second - temp.first + 1);
    }
};



// 2.1 中心扩展法（优化前的）
class Solution {
public:
    int max_size =0;
    pair<int, int> temp{0,0};
    void act(string& s, int left, int right) {
        if(left == right) {
            left = left-1;
            right = right+1;
        }
        while(left >= 0 && right < s.size()) {
            if(s[left] == s[right]) {
                if(right-left+1 > max_size) {
                    max_size = right-left+1;
                    temp.first = left;
                    temp.second = right;
                }
                left--;
                right++;
            }
            else    return;
        }       
    }

    string longestPalindrome(string s) {
        int n = s.size();
        for(int i = 0; i < n-1; ++i) {
            act(s, i, i);  //不能用最后一个元素作为中心（就算用了值才为1，无伤大雅），随便返回一个长度为1的字串。初始化temp的时候考虑到了
            act(s, i, i+1);
        }
        return s.substr(temp.first, temp.second-temp.first+1);
    }
};



